#include <algorithm>
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<vector<int>>dp(triangle.size(),vector<int>(triangle.size()));
        dp[0][0]=triangle[0][0];
        for(int i=1;i<triangle.size();i++)
        {
            dp[i][0] = dp[i - 1][0] + triangle[i][0];
            for(int j=1;j<i;j++)
            {
                dp[i][j]=min(dp[i-1][j-1]+triangle[i][j],dp[i-1][j]+triangle[i][j]);
            }
            dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
        }
        int t=INT_MAX;
        for(int i=0;i<triangle.size();i++)
        {
            if(t>dp[triangle.size()-1][i])t=dp[triangle.size()-1][i];
        }
        return t;
    }
};
